package com.chj.jz.dp.class02;

// https://www.lintcode.com/problem/longest-continuous-increasing-subsequence/description
public class Code04_LongestContinuousIncreasingSubsequence {
	public static int LIS(int[] arr, int n) {
		int i;
		int[] f = new int[n];
		int res = 0;

		for (i = 0; i < n; i++) {
			f[i] = 1;
			if (i > 0 && arr[i] > arr[i - 1]) {
				f[i] = f[i - 1] + 1;
			}

			res = Math.max(res, f[i]);
		}

		return res;
	}

	public static int longestContinuousIncreasingSubsequence(int[] arr) {
		int n = arr.length;
		if (n == 0) {
			return 0;
		}

		int r1 = LIS(arr, n);

		int i, j, t;
		i = 0;
		j = n - 1;
		while (i < j) {
			t = arr[i];
			arr[i] = arr[j];
			arr[j] = t;
			i++;
			j--;
		}

		int r2 = LIS(arr, n);
		return r1 > r2 ? r1 : r2;
	}

	public static void main(String[] args) {
		{
			int[] arr = new int[] { 5, 4, 2, 1, 3 };
			System.out.println(longestContinuousIncreasingSubsequence(arr));
		}
		{
			int[] arr = new int[] { 5, 1, 2, 3, 4 };
			System.out.println(longestContinuousIncreasingSubsequence(arr));
		}
	}
}
